package com.c2b.algorithm.newcoder.double_pointer;

/**
 * <a href="https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=295&tqId=658&ru=%2Fpractice%2F75e878df47f24fdc9dc3e400ec6058ca&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj">合并两个有序的数组</a>
 * <p>给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组</p>
 * <p>数据范围：0≤n,m≤100，∣A[i]∣<=100，∣B[i]∣<=100</p>
 * <p>
 * <b>注意：</b><br>
 * 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n<br>
 * 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印<br>
 * 3. A 数组在[0,m-1]的范围也是有序的<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/15 14:18
 */
public class BM0087Merge_S {

    public void merge(int[] A, int m, int[] B, int n) {
        // 从A的末尾节点和B的末尾节点开始。找出较大值放到A数组的尾部
        int aIndex = m - 1;
        int bIndex = n - 1;
        int index = m + n - 1;
        // 排除了B中元素为空的情况
        while (aIndex >= 0 && bIndex >= 0) {
            if (A[aIndex] <= B[bIndex]) {
                A[index--] = B[bIndex--];
            } else {
                A[index--] = A[aIndex--];
            }
        }
        // A中元素为空的情况
        if (aIndex < 0) {
            while (bIndex >= 0) {
                A[index--] = B[bIndex--];
            }
        }
    }

    public static void main(String[] args) {
        BM0087Merge_S bm0087Merge_s = new BM0087Merge_S();
        int[] ints = {1, 2, 3, 0, 0, 0};
        bm0087Merge_s.merge(ints, 3, new int[]{2, 5, 6}, 3);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

}
